#include "StdAfx.h"
#include "Graph.h"
//--Khai bao thu vien doc file
#include "iostream"
#include "fstream"
using namespace std;
//--

//--Ham doc file
void Graph::GetData(char *filename)
{
	ifstream fin;
	fin.open(filename);
	//--Dinh xuat phat
	fin >> k;
	//--
	//--So dinh cua do thi
	fin >> N;
	//--
	//--Khoi tao ma tran ke cua do thi
	A.resize(N);
	//--
	//--Khoi tao bien variable_1
	int variable_1 = 0;
	//--
	for (int i = 0; i < N; i++)
	{
		for(int j = 0; j < N; j++)
		{
			fin >> variable_1;
			A[i].push_back(variable_1);
		}
	}
	fin.close();
	//--Khoi tao mang luu cac dinh
	for(int i = 0; i < N; i++)
	{
		Labels.push_back(-1);
	}
	//--
}
//--
//--Ham Check_x_to_i 
bool Graph::Check_x_to_i(int x, int i)
{
	bool flag = false;
	if (A[x][i] != 0)
	{
		flag = true;
		return flag;
	}
	return false;
}
//--
//--Ham xuat man hinh
void Graph::OutScreen()
{
	printf("%d\n",weight);
	int n = paths.size();
	for (int i = 0; i < n; i++)
	{
		printf("%d ",paths[i]);
	}
	printf("\n");
}
//--
//--Ham ghi file
void Graph::WriteData(char *filename, bool flag)
{
	ofstream fin;
	fin.open(filename);
	if (flag)
	{
		int n = paths.size();
		fin << weight;
		fin << "\n";
		for(int i = 0; i < n; i++)
		{
			fin << paths[i];
			fin << " ";
		}
		fin << "\n";
	}
	else
	{
		fin << "NULL";
		fin << "\n";
	}
	fin.close();
}
//--
//--Ham FindHamiltonPath
bool Graph::FindHamiltonPath(int nCount, int x, vector<int> &path)
{
	//--Buoc 1 : Kiem tra neu so lan goi de quy lon hon so dinh cua do thi va
	//ton tai canh noi tu x toi dinh dau tien trong duong di thi ket luan co chu trinh Hamilton
	if (nCount == N)
	{
		if (A[k][x] != 0)
		{
			weight = weight + A[k][x];
			//--Ta co mot chu trinh Hamilton
			return true;
			//--
		}
		else
		{
			return false;
		}
	}
	//--
	//--Buoc 2 : Duyet qua tat ca cac dinh i (chua xet) ke voi dinh x
	for (int i = 0; i < N; i++)
	{
		if (Check_x_to_i(x,i) == true) //-->Neu ton tai canh noi tu x toi i
		{
			if (Labels[i] == -1) //-->Neu i chua duoc ghe tham
			{
				//--Buoc 3 : Luu lai dinh i trong duong di va danh dau i da xet. Goi de quy tim tiep
				path[nCount] = i; //-->Luu lai dinh i trong duong di
				weight = weight + A[x][i]; //-->Luu lai chieu dai cua chu trinh
				Labels[i] = 0; //-->Danh dau dinh i da xet
				if(FindHamiltonPath(nCount + 1, i, path))
				{
					return true;
				}
				else
				{
					return false;
				}
				//--Buoc 4 : Bo danh dau dinh i da xet
				//Labels[i] = -1;
			}
			//--
		}
		//--
	}
	//--
}
//--
//--Ham HamiltonPath
bool Graph::HamiltonPath()
{
	//--Lan luot xet cac dinh cua do thi
	//for(int i = 0; i < N; i++)
	//{
	//--Khoi tao paths
	paths.resize(N);
	//--
	paths[0] = k;
	//--Danh dau da ghe tham
	Labels[k] = 0;
	//--
	//--Khoi tao chieu dai cua chu trinh
	weight = 0;
	//--
	//--Neu tim thay chu trinh Hamilton
	if (FindHamiltonPath(1,k,paths))
	{
		return true;
	}
	else
	{
		return false;
	}
	//--
	//--Xoa danh dau da ghe tham x
	//Labels[i] = 0;
	//--
	//}
	//--
}
//--
